//
//  LinkListExt.cpp
//  DataStructure
//
//  Created by 舒磊明 on 2020/6/22.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#include "LinkListExt.hpp"

// 删除不带头节点单链表中所有x的结点(递归)
void removex(LinkList &L, int x)
{
    if (L == nullptr) {
        return;
    }
    if (L->data == x) { // 递归删除
        LNode *p = L;
        L = L->next;
        free(p);
        removex(L, x);
    } else { // 递归调用
        removex(L->next, x);
    }
}

// 带头结点，删除值为x的结点
void removeX2(LinkList &L, int x)
{
    LNode *pre = L;         // 指针的上一个
    LNode *p = pre->next;   // 遍历指针

    while (p != NULL) {
        if (p->data == x) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            pre = p;
            p = pre->next;
        }
    }
}

// 带头结点，反向输出(递归)
// 不让破坏表则用递归，否则逆序再输出
void reversePrint(LinkList L)
{
    if (L != nullptr) {
        reversePrint(L->next);
        std::cout<<L->data<<std::endl;
    }
}

// 带头结点，删除最小值
void delMin(LinkList &L)
{
    if (L == NULL || L->next == NULL) {
        return;
    }
    LNode *pre = L;     // 循环指针前驱
    LNode *p = L->next; // 循环指针
    int min = p->data;  // 最小值
    LNode *min_pre = L; // 最小值前驱指针
    LNode *min_p = p;   // 最小值指针

    while (p != NULL) {
        if (p->data < min) {
            min = p->data;
            min_pre = pre;
            min_p = p;
        }
        pre = p;
        p = pre->next;
    }

    min_pre->next = min_p->next;
    free(min_p);
}

// 带头节点，逆序
void reverse(LinkList &L)
{
    if (L == NULL)
        return;
    
    LinkList p = L->next, r = p;
    L->next = NULL;
    
    while (p) {
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
}

// 带头结点，递增(O^2) S(1)
// 或者把元素插入数组中先排序后插入单链表，O(nlog2)S(n)
void orderList(LinkList &L)
{
    // 右侧插入左侧
    if (L == NULL)
        return;
    
    LinkList p = L->next, r = p;
    LinkList head = L; // 指向头节点
    L->next = NULL;
    
    while (p != NULL) {
        head = L;
        r = p->next;
        while (head->next != NULL && head->next->data < p->data) {
            head = head->next;
        }
        p->next = head;
        head->next = p;
        p = r;
    }
}

// 带头结点，删除值在s～t之间的结点
void rangeDel(LinkList &L, int s, int t)
{
    if (L->next == nullptr) {
        return;
    }
    LNode *pre = L;     // 循环指针的前驱
    LNode *p = L->next; // 循环指针

    while (p != nullptr) {
        if (p->data >= s && p->data <= t) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

// 找出公共结点
int ListLen(LinkList L) // 获取表长
{
    LNode *p = L;
    int len = 0;
    while (p != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}
LinkList commonNode(LinkList L1, LinkList L2)
{
    // 计算2链表的长度len1,len2 时间复杂度：O(n)
    // 设置2个工作指针，长表优先向后遍历|len1 - len2|个元素
    int len1 = ListLen(L1), len2 = ListLen(L2), abs = 0;
    LNode *long_list, *short_list;
    if (len1 > len2) {
        long_list = L1;
        short_list = L2;
        abs = len1 - len2;
    } else {
        long_list = L2;
        short_list = L1;
        abs = len2 - len1;
    }
    while (abs > 0) {   // 长表优先遍历
        long_list = long_list->next;
        abs--;
    }
    while (long_list != nullptr && short_list != nullptr) {
        if (long_list == short_list) { // 返回公共节点
            return long_list;
        }
        long_list = long_list->next;
        short_list = short_list->next;
    }
    return nullptr;
}

// 带头节点，递增输出并释放元素
void printAndFree(LinkList &L)
{
    // p为工作指针，pre指向最小值前面的元素
    LNode *p, *pre;
    while (L->next != nullptr) {
        p = L;
        pre = L;
        while (p->next != nullptr) {
            if (p->next->data < pre->next->data)
                pre = p;
            p = p->next;
        }
        printf("%d\n", pre->next->data);
        p = pre->next;
        pre->next = p->next;
        free(p);
    }
    free(L);
}

// 带头节点，A拆分为A和B，A包含奇数号元素，B包含偶数号元素，顺序不变
void splitList(LinkList L)
{
    // 遍历L，将奇数元素尾插入A，偶数元素偶插入B
    LinkList A = (LinkList)malloc(sizeof(LinkList));
    LinkList B = (LinkList)malloc(sizeof(LinkList));
    A->next = NULL;
    B->next = NULL;
    
    LinkList p = L->next, pa = A, pb = B;
    int count = 1;
    
    while (p) {
        LinkList s = (LinkList)malloc(sizeof(LinkList));
        s->data = p->data;
        s->next = NULL;
        if (count % 2 == 1) {
            s->next = pa->next;
            pa = s;
        } else {
            s->next = pb->next;
            pb = s;
        }
    }
}

// C={a1 b1 a2 b2 ... an bn} => A = {a1 a2 ...}, B = {bn ... b2 b1}
void splitList2(LinkList L)
{
    // 奇数号插入A，偶数号插入B，同上
    // 循环L，奇数号尾插法插入A，偶数号头插法插入B O(n)
    if (L == nullptr) {
        return;
    }
    LNode *p = L->next;
    int k = 1;
    LinkList A;
    LinkList B;
    InitList(A);
    InitList(B);
    LNode *ra = A;
    
    while (p != nullptr) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = p->data;
        if (k % 2 == 0) {
            s->next = B->next;
            B->next = s;
        } else {
            s->next = ra->next;
            ra->next = s;
            s = ra;
        }
    }
}

// 带头节点的递增的单链表，删除重复的元素
void DelRepeat(LinkList &L)
{
    
    LinkList p = L->next, pre = L;
    while (p != NULL) {
        if (p->next && p->data == p->next->data) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

// ✨两个递增的单链表，合并为递减的单链表。要求使用原节点合并
void mergeList(LinkList &L1, LinkList &L2, LinkList L)
{
    // L1和L2第一个较小的元素使用头插法插入L
    LinkList p1 = L1->next, p2 = L2->next;
    while (p1 && p2) {
        if (p1->data <= p2->data) {
            L1->next = p1->next;
            p1->next = L->next;
            L->next = p1;
            p1 = L1->next;
        } else {
            L2->next = p2->next;
            p2->next = L->next;
            L->next = p2;
            p2 = L2->next;
        }
    }
    // 将L1、L2剩余的元素插入L
    while (p1) {
        L1->next = p1->next;
        p1->next = L->next;
        L->next = p1;
        p1 = L1->next;
    }
    while (p2) {
        L2->next = p2->next;
        p2->next = L->next;
        L->next = p2;
        p2 = L2->next;
    }
}

// ✨✨A，B为递增单链表，用公共节点创建C。不破坏A和B
void mergeCommom(LinkList L1, LinkList L2)
{
    if (L1 == nullptr || L2 == nullptr) {
        return;
    }
    LNode *p1 = L1->next;
    LNode *p2 = L2->next;
    LinkList L;
    InitList(L);
    LNode *r = L;
    
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->data == p2->data) {
            LNode *s = (LNode*)malloc(sizeof(LNode));
            s->data = p1->data;
            s->next = r->next;
            r->next = s;
            r = s;
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->data > p2->data) {
            p2 = p2->next;
        } else {
            p1 = p1->next;
        }
    }
}

// A,B为递增单链表，求交集，并存放于A中
void intersection(LinkList &L1, LinkList &L2)
{
    // 如果p1 == p2 下一个
    // 如果p1 > p2 p2往后移动
    // 如果p1 < p2 删除p1
    LinkList p1 = L1->next, p2 = L2->next, pre = L1;
    while (p1 && p2) {
        if (p1->data == p2->data) {
            pre = p1;
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->data > p2->data) {
            p2 = p2->next;
        } else {
            pre->next = p1->next;
            free(p1);
            p1 = pre->next;
        }
    }
    // 释放A中剩余的节点
    while (p1) {
        pre = p1->next;
        free(p1);
        p1 = pre->next;
    }
}

// ✨A=a1,a2...an, B=b1,b2...bm；判断B是否为A的子序列。
bool isSubList(LinkList L1, LinkList L2)
{
    // 暴力法
    LinkList p1 = L1->next, p2 = L2->next, p = L1->next;
    while (p1 && p2) {
        if (p1->data == p2->data) {
            p1 = p1->next;
            p2 = p2->next;
        } else {
            p2 = L2->next;
            p = p->next;
            p1 = p;
        }
    }
    return p2 == NULL;
}

// ✨判断循环双链表是否对称
bool isMirror(DLinkList L)
{
    // 定义2各指针，指向头和尾
    // 向中间移动，并比较是否相同
    Lnode *p = L;
    Lnode *r = L->prior;
    
    while (p != r) {
        if (p->data != r->data) {
            return false;
        } else {
            p = p->next;
            r = r->prior;
        }
    }
    return true;
}

// 2个循环单链表L1和L2，将L2链到L1上后，依然为单链表
void mergeLoopList(LinkList &L1, LinkList &L2)
{
    LNode *r1 = L1, *r2 = L2;
    while (r1->next != L1) {
        r1 = r1->next;
    }
    while (r2->next != L2) {
        r2 = r2->next;
    }
    r1->next = L2;
    r2->next = L1;
}

// 带头节点，循环单链表，data为正整数，找出最小值，删除输出。直到表为空，最后删除头节点。
void PrintAndDelete(LinkList &L)
{
    // O(n^2)算法
    // 遍历找到最小值，依次删除。
    if (L == nullptr) {
        return;
    }
    
    LNode *p, *pre, *min, *minPre;
    
    while (L->next != L) {
        pre = L;
        p = pre->next;
        minPre = pre;
        min = minPre->next;
        
        while (p != L) {
            if (p->data < min->data) {
                minPre = pre;
                min = minPre->next;
            }
            pre = p;
            p = p->next;
        }
        std::cout<<min->data<<std::endl;
        minPre->next = min->next;
        free(min);
    }
    free(L);
}


// 带有头指针非循环双链表，访问一次freq+1，并保持按照freq递减排序。
void Swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

FDNode* Locate(FDLinkList L, int x)
{
        // 先循环查找到元素，然后freq+1，最后对L进行排序。返回找到的元素
    if (L == nullptr) {
        return nullptr;
    }
    FDNode *p = L->next;
    while (p && p->data != x) { // 找到元素
        p = p->next;
    }
    if (p->data == x) {
        p->freq++;
        // 将p摘下，找到插入位置，保证同频率p排在第一
        if (p->next != nullptr) {
            p->next->pred = p->pred;
        }
        p->pred->next = p->next;
        FDNode *q = p->pred;
        while (q != L && q->freq <= p->freq) {
            q = q->pred;
        }
        p->next = q->next;
        q->next->pred = p;
        p->pred = q;
        q->next = p;
        return p;
    } else { // 未找到元素则返回空
        return nullptr;
    }
}

// 带头节点单链表，找到倒数第k个位置上的元素，如果查找成功，输出data，返回1，否则返回0
bool searchElem(LinkList L, int k)
{
    // 1.让p指向第k个节点，pre指向头节点。p和pre相差k个节点
    // 2.p和pre同时向后移动，直到p指向null，此时pre指向倒数第k个节点
    LinkList p = L->next, pre = L;
    for (int i = 0; p && i < k; i++) p = p->next;
    if (p == NULL)
        return 0;
    while (p) {
        p = p->next;
        pre = pre->next;
    }
    // visit(pre);
    return 1;
}

// ✨带头节点的单链表保存单词，如果有相同后缀则共享后缀。
// str1和str2分别指向两个单链表头节点，请高效地找到同节点的起始位置
int listlen(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}
LNode* searchExt(LinkList str1, LinkList str2)
{
    // 使用双指针法，p和q分别遍历
    // 先获取长度n1，n2，然后长链表的指针先往后遍历|n1-n2|
    // 然后p和q同时往后直到相同为止
    // O(n)
    LNode *p1 = str1, *p2 = str2;
    // 获取长度
    int n1 = listlen(str1);
    int n2 = listlen(str2);
    // 指向长链表的先遍历
    p1 = str1->next;
    p2 = str2->next;
    if (n1 > n2) {
        for (int i = 0; i < n1 - n2; i++) {
            p1 = p1->next;
        }
    } else {
        for (int i = 0; i < n2 - n1; i++) {
            p2 = p2->next;
        }
    }
    // 找公共节点
    while (p1 != nullptr && p2 != nullptr && p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    if (p1 && p2) {
        return p1;
    }
    return nullptr;
}

// 单链表保存m个数，|data| <= n
// 高效算法对于绝对值相同的节点，只保留第一个
void removeNumber(LinkList &L, int n)
{
    // 1.遍历链表，同时记录已出现的值
    // 2.如果出现相同的值，则删除该节点
    int arr[n];
    for (int i = 0; i < n; i++)
        arr[i] = 0; // 数组初始化为0

    LinkList p = L->next, pre = L;
    while (p) {
        if (arr[abs(p->data) - 1] == 1) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            arr[abs(p->data) - 1] = 1;
            p = p->next;
        }
    }
}

// ✨判断链表是否有环，若有则返回环的入口
LNode* findLoop(LinkList L)
{
    // 设置两个指针low和fast，low一次走一步，fast一次走2步
    // 如果有环，则low和fast一定会相遇。
    // 找环的入口：
    // slow和fast相遇，slow最多刚好走完一圈
    // 链表长度为L，设头节点距离入口长度为a，相遇点距离入口x，环的长度为l，fast走了n圈,则有
    // slow走过的路程为：a + x
    // fast走过的路程为：a + x + n*l = 2*(a + x)
    // a + x = n*l = (n-1)*l + (L - a)
    // a = (n-1)*l + (L - a - x)
    // L-a-x = 相遇点到入口的距离 = a = 起点到入口的距离
    
    // 思路2:1.计算环的长度l，p1先走l
    // 2.p1和p2同时移动，直到相遇则为入口节点
    
    LNode *low = L->next, *fast = L->next;
    while (fast->next != nullptr) {
        low = low->next;
        fast = fast->next->next;
        if (low == fast) {
            break;
        }
    }
    if (fast->next == nullptr) {
        return nullptr;
    }
    LNode *p = L, *q = low;
    while (p != q) {
        p = p->next;
        q = q->next;
    }
    return p;
}

// ✨带头节点单链表，L={a1,a2...an} -> L={a1,an,a2,an-1,a3,an-2...}
// 要求S(1)并且高效
void ListSort(LinkList &L)
{
    // 将单链表L断开，工作指针将下标为偶数的元素头插法插入L
    // 此时L链表为逆序的偶元素，re链表指向奇元素
    // 再将剩下的元素间隔插入L中
    // O(n),S(1)
    LNode *p = L->next, *re = L->next,*r;
    int k = 1;
    L->next = nullptr;
    while (p != nullptr) {
        if (k % 2 == 0) {
            r = p->next;
            p->next = L->next;
            L->next = p;
            p = r;
        } else {
            p = p->next;
        }
        k++;
    }
    p = re; // 让p指向re，此时链表中为奇数元素
    r = L;  // 辅助指针p完成间隔插入
    while (p != nullptr) {
        re = p->next;
        p->next = r->next;
        r->next = p;
        p = re;
        if (r->next->next == nullptr) { // 若偶元素为null，说明此时p也指向null
            break;
        }
        r = r->next->next;
    }
}
